package leetcode.code0354;

import java.util.Arrays;

import leetcode.IDebug;

public class Solution implements IDebug {

	public int maxEnvelopes(int[][] envelopes) {
		Arrays.sort(envelopes, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
		int len = envelopes.length;
		int[] ends = new int[len];
		int p = 0;
		for (int i = 0; i < len; i++) {
			int cur = envelopes[i][1];
			if (p==0 || cur > ends[p - 1]) {
				ends[p++] = cur;
			} else {
				int l = 0, r = p - 1;
				int ans = 0;
				while (l <= r) {
					int mid = l + ((r - l) >> 1);
					if (ends[mid] >= cur) {
						ans = mid;
						r = mid - 1;
					} else {
						l = mid + 1;
					}
				}
				ends[ans] = cur;
			}
		}
		return p;
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
